A scheduler in an operating system of a processing device schedules a plurality of processing threads (“threads”) for processing by one or more processors (“cores”) in the processing device. A thread has a scheduling state and a thread processing context. The scheduling state can include a variety of attributes such as a processing priority for the thread, a quantum of time that a processor will work on the thread before scheduling another thread for the processor, and other attributes. A thread context for can include storage corresponding to one or more processor registers. The data in the storage can represent the state of the corresponding processor registers when the thread was last processed by a processor. Thread context can further include other thread-specific variables and information.
As is known in the art, during a critical section of a first thread, the first thread may hold a mutual exclusion flag (“mutex”) on a resource, such as a write-lock on a record of a database. For example, the critical section may include the completion of a write operation of the record to a database. A second thread may include a read operation on the database, e.g., to read the record from the database. The first thread holds the mutex on the database record so that the first process can complete writing the database record before another thread can read the record. The scheduler will block the second thread, and put the second thread on a wait queue, while the second thread is waiting for the first thread to release the mutex on the resource (e.g., record). While on the wait queue, the second thread is removed from consideration by the scheduler as a thread that may be selected for processing. A “priority inversion” occurs when the first thread that holds the mutex on the resource has as lower scheduling state priority than the second thread that is waiting on the release of the mutex so that the second thread may perform processing using the resource (e.g., record). A priority inversion reduces overall processing performance because the scheduler will select higher priority threads for processing before the processing the lower priority thread holding the mutex, but a higher priority thread is blocked, waiting on the release of the mutex held by the lower priority thread.
There are at least two methods to resolve a priority inversion in the prior art. First, do nothing and simply wait for the lower priority thread to release the mutex. This solution is undesirable, particularly when the blocked higher priority thread that is waiting on the mutex has a very high priority relative to the thread holding the mutex. The second method to resolve a priority inversion involves active steps by the scheduler.
Schedulers in the prior art detect the priority inversion, dequeue the first thread from the run queue, and assign the first thread the higher priority of the second thread that is blocked, waiting on the first thread to release the mutex. The scheduler can then reschedule the first thread using the higher priority of the second thread. The second thread is then put on a wait queue. In some systems of the prior art, the first thread may never be restored to its previous, lower priority. After the first thread has been scheduled in the run queue, and the first thread has been processed to the point that the first thread finishes its critical section and releases the mutex on the resource, then the second thread is woken up from the wait queue and the second thread can be scheduled on the run queue. In some systems of the prior art, after resolving the priority inversion, the first thread and the second thread will both have the same processing priority. Further, some schedulers use many variables to determine a final effective scheduler priority for threads, and may adjust those variables on a frequent basis. The scheduler will have to then reflect those changes onto the borrowed priorities of resource-holding threads.